10 09/2014 twitter puddle 最后更新: Wed Sep 10 2014 12:37:50 GMT+0800 水坑算法 题目 如图,如果 数组是墙,问:下雨墙之间能积多少水? 显示算法 观察计算过程 循环,从两头开始(leftMax,rightMax) 找到低的那个 和旁边(左边+1;右边-1)比较,如果比我低,会存水,并且 水= 哥两儿相减。如果旁边比我高,存不住水,向外侧流走了。因为我是两头中间低的那个,所以,旁边比我低的就是存水。 下一个 代码: function maxWater(arr) { var left = 0, right = arr.length - 1, leftMax = arr[left], rightMax = arr[right], volume = 0; while (left < right) { if (leftMax < rightMax) { var height = arr[++left]; leftMax = Math.max(leftMax, height); volume += leftMax - height; } else { var height = arr[--right]; rightMax = Math.max(rightMax, height); volume += rightMax - height; } } return volume; } via https://gist.github.com/mkozakov/59af0fd5bddbed1a0399